package _02_linked_list.exerc;

/**
 * @author: mornd
 * @dateTime: 2023/6/3 - 20:39
 * 工具类
 */
public abstract class ListNodes {

    /**
     * 反转链表
     * @param p
     * @return
     */
    public static ListNode reverses(ListNode p) {
        if(p == null || p.next == null) {
            return p;
        }
        ListNode last = reverses(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }

    /**
     * 递归合并
     *
     * @param arr
     * @return
     */
    public static ListNode mergeMulti(ListNode... arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        return split(arr, 0, arr.length - 1);
    }

    private static ListNode split(ListNode[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        int m = (i + j) >>> 1;
        ListNode left = split(arr, i, m);
        ListNode right = split(arr, m + 1, j);
        return merge(left, right);
    }

    /**
     * 合并两个有序链表
     * @param list1
     * @param list2
     * @return
     */
    static ListNode merge(ListNode list1, ListNode list2) {
        ListNode s = new ListNode();
        /*
            s 表示创建的新链表，存储 list1 + list2 合并的数据
            p 表示 s 中最后一个非空元素下标，下次插入直接指定 p.next
         */
        ListNode p = s;
        ListNode p1 = list1;
        ListNode p2 = list2;

        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return s.next;
    }
}
